首页 > 试题广场 >

编程题2

[编程题]编程题2

热度指数：12804 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。

输入描述:

第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。

输出描述:

输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。

示例1

输入

8 1
aabaabaa

输出

说明

把第一个 'b' 或者第二个 'b' 置成 'a'，可得到长度为 5 的全 'a' 子串。

算法知识视频讲解

Python 3

牛客461687564号

def length(c,m,n):
l=[]
if len(c)<=m:
return n
else:
for i in range(0,len(c)-m+1):
if i==0:
l.append(c[i+m])
elif i+m==len(c):
l.append(n-1-c[i-1])
else:
l.append(c[i+m]-c[i-1]-1)
res=0
# print(len(l))
for x in l:
if x>res:
res=x
return res

n,m=map(int,input().split())
s=input()
cnt=0
cnt=s.count('a')
#print(cnt)
c=[]
d=[]
#if cnt<=len(s)-cnt:
c.append(s.find('a'))
while c[-1]!=-1:
c.append(s.find('a',c[-1]+1))
c.pop()
# print(len(c))
#print(c)

#print(length(c,m,n))
#else:
d.append(s.find('b'))
while d[-1]!=-1:
d.append(s.find('b',d[-1]+1))
d.pop()
#print(len(c))
#print(c)
print(max(length(c,m,n),length(d,m,n)))

发表于 2022-08-18 18:08:04 回复(0)